package L614;

import util.ListNode;

/**
 * @program: javase
 * @description: 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
 * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 * @author: luolidong
 * @create: 2021-06-14 15:08
 * @version: 1.0
 */
public class Demo4 {
    //    1 2 3 4 5
//    1 4 3 2 5
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
//        求left前一个
        ListNode cur = dummy;
//        left=2
        for (int i = 1; i < left; i++) {
            cur = cur.next;
        }
        ListNode preNode = cur;
        ListNode start = cur.next;

        cur = dummy;
        for (int i = 0; i < right; i++) {
            cur = cur.next;
        }
        ListNode end = cur;
        ListNode afterNode = cur.next;
// 要反转的链表断开
        end.next = null;
//        记录反转后的尾结点
        ListNode newHead = start;
//反转
        preNode.next = reverse(start);
//尾结点指向后面元素
        newHead.next = afterNode;
        return dummy.next;

    }

    public ListNode reverse(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        ListNode listNode = new Demo4().reverseBetween(ListNode.build(), 2, 4);
//        ListNode listNode = new Demo4().reverse(ListNode.build());
        System.out.println(listNode);
    }
}
